package jfreechart.tsp.arithmetic;

import jfreechart.tsp.ui.ComprehensiveChart;
import jfreechart.tsp.ui.Point;
import jfreechart.tsp.ui.Segment;
import org.jfree.ui.RefineryUtilities;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;


//粒子群算法实现TSP问题
//同蚁群算法一样,得到最优解的迭代次数差别很大,总的来说,此算法比蚁群算法随机性更大,极不稳定.难以控制和调优,很难得到最优解
//交换序的粒子群算法只适合小规模的TSP问题,交换序的粒子群算法,怎么看都像是变种的遗传算法
@SuppressWarnings("unchecked")
public class ParticleSwarm {

    int TOUR_TIMES = 200;//迭代次数
    int PARTICLE_NUM = 500;//粒子数量:粒子多少就像种群数量,多样性好也是有利于获取好的结果
    int CITY_NUM;//城市数量(动态)
    double[][] distence;//城市间距离矩阵
    Tour[] tours;//粒子列表
    Tour bestTour = new Tour();//全局历史最优解
    Tour tour = new Tour();//原始个体
    //粒子群算法核心处理
    int m = 0;//没有获取到更优解的次数
    int f = 0;//进化次数
    double w = 0.9;
    double r = 0.9;
    boolean flag = false;//一代有没有获取到更优解
    boolean pflag = true;//打印标识
    HashSet<Point> pointSet = new HashSet<Point>();
    List<Segment> segments = new ArrayList<Segment>();//所有线段集合
    private ArrayList<ArrayList<SwapSequence>> randomSeq = new ArrayList<ArrayList<SwapSequence>>();//粒子初始交换序列

    public static void main(String[] args) {
        new ParticleSwarm().start();
    }

    void init() {
        int n = 0;
        tour.cities.clear();
        tour.addCity(new City(n++, 60, 200));
        tour.addCity(new City(n++, 180, 200));
        tour.addCity(new City(n++, 80, 180));
        tour.addCity(new City(n++, 140, 180));
        tour.addCity(new City(n++, 20, 160));
        tour.addCity(new City(n++, 100, 160));
        tour.addCity(new City(n++, 200, 160));
        tour.addCity(new City(n++, 140, 140));
        tour.addCity(new City(n++, 40, 120));
        tour.addCity(new City(n++, 100, 120));
        tour.addCity(new City(n++, 180, 100));
        tour.addCity(new City(n++, 60, 80));
        tour.addCity(new City(n++, 120, 80));
        tour.addCity(new City(n++, 180, 60));
        tour.addCity(new City(n++, 20, 40));
        tour.addCity(new City(n++, 100, 40));
        tour.addCity(new City(n++, 200, 40));
        tour.addCity(new City(n++, 20, 20));
        tour.addCity(new City(n++, 60, 20));
        tour.addCity(new City(n++, 160, 20));

        CITY_NUM = tour.cities.size();

        //初始化城市距离
        distence = new double[CITY_NUM][CITY_NUM];
        for (int i = 0; i < CITY_NUM; i++) {
            for (int j = i; j < CITY_NUM; j++) {
                if (i == j) {
                    distence[i][j] = 0;
                } else {
                    distence[i][j] = distence[j][i] = tour.cities.get(i).distTo(tour.cities.get(j)); //对称TSP
                }
            }
        }

        //初始化粒子群
        int x, y, z;
        ArrayList<SwapSequence> list = null;
        tours = new Tour[PARTICLE_NUM];
        for (int i = 0; i < tours.length; i++) {
            tours[i] = new Tour(tour.cities, distence);

            //初始化粒子初始交换序列(起类似突变的作用,丰富种群多样性)
            list = new ArrayList<SwapSequence>();
            z = (int) (Math.random() * CITY_NUM);
            for (int j = 0; j < z; j++) {
                x = (int) (Math.random() * CITY_NUM);
                y = (int) (Math.random() * CITY_NUM);
                while (x == y) {
                    y = (int) (Math.random() * CITY_NUM);
                }
                list.add(new SwapSequence(x, y));
            }
            randomSeq.add(list);
        }

        update();//更新全局最优
    }

    Tour pso() {
        List<SwapSequence> ss = new ArrayList<SwapSequence>();//交换序列表
        List<SwapSequence> tmp = null;
        double adjustRate = 0.5;//使前期突变频率高,后期突变频率降低
        for (int i = 0; i < TOUR_TIMES; i++) {
            for (int j = 0; j < PARTICLE_NUM; j++) {
                ss.clear();
                //速度向量:V[i+1]=V[i]*w+c1*r1(Pbest[i]-X[i])+c2*r2(Gbest-X[i])
                //V[i]*w
                tmp = randomSeq.get(j);//相当于突变,产生新的个体
                if (i % 2 == 0 && adjustRate < 1) {
                    adjustRate *= (1 + 0.1);//每两代加X%的概率,趋于收敛
                }
                if (adjustRate > w) {
                    adjustRate = w;//比率不能超过最高概率
                }
                ss.addAll(subSwapSequences(tmp));
                if (Math.random() > adjustRate) {
                }
//                ss.addAll(tmp);
                //r1(Pbest[i]-X[i])
                tmp = tours[j].minus(tours[j].best);//
                if (Math.random() > r) {
                    ss.addAll(tmp);
                }
//                ss.addAll(subSwapSequences(tmp));
                //r2(Gbest-X[i]
                tmp = tours[j].minus(bestTour.cities);
//                ss.addAll(subSwapSequences(tmp));
                if (Math.random() > r) {
                    ss.addAll(tmp);
                }
//                ss.addAll(tmp);//加速收敛
                for (SwapSequence swapSequence : ss) {
                    tours[j].swap(tours[j].cities, swapSequence.x, swapSequence.y); //位置向量:X[i+1]=X[i]+V[i]  类似交叉
                }

                tours[j].update();//更新局部最优解 类似选择
            }
            flag = update();//更新全局最优解  类似选择

            if (flag) {
                m++;//这一代没有获取到更优解
            } else {
                if (m > 3) {
                    f++;//产生进化
                    pflag = true;
                }
                m = 0;
            }

            if (m > 3 && pflag) {
                for (int j = 0; j < CITY_NUM; j++) {
//                  System.out.println(Arrays.toString(pheromone[j]));
                }
                bestTour.dist = 0;
                System.out.println(i + " " + f + " " + bestTour.bestDist);
                pflag = false;
            }
        }
        return bestTour;
    }

    //随机截取部分交换序列
    private List<SwapSequence> subSwapSequences(List<SwapSequence> ss) {
        int start = (int) (Math.random() * ss.size());
        int end = (int) (Math.random() * ss.size());
        int tmp = start > end ? start : end;
        start = start < end ? start : end;
        end = tmp;
        return ss.subList(start, end);
    }

    //更新全局最优解
    private boolean update() {
        int idx = -1;
        for (int i = 0; i < tours.length; i++) {
            if (tours[i].getDistence() < bestTour.bestDist) {
                idx = i;
            }
        }
        if (idx >= 0) {
            bestTour.cities = (ArrayList<City>) tours[idx].cities.clone();
            bestTour.bestDist = tours[idx].getDistence();
            return false;
        }
        return true;
    }

    //展示前的数据准备
    void initView(Tour tour) {
        segments.clear();//防止数据叠加
        City tmp = tour.cities.get(0);
        Point start = new Point(tmp.x, tmp.y);
        pointSet.add(start);
        Point end = null;
        for (int i = 1; i < tour.cities.size(); i++) {
            end = new Point(tour.cities.get(i).x, tour.cities.get(i).y);
            segments.add(new Segment(start, end));
            tmp = tour.cities.get(i);
            start = end;
            pointSet.add(start);
        }
    }

    void view(Tour tour) {
        initView(tour);//展示前的数据准备
        ComprehensiveChart demo = new ComprehensiveChart("Test", pointSet, segments);
        demo.pack();
        RefineryUtilities.centerFrameOnScreen(demo);
        demo.setVisible(true);
    }

    void start() {
//        for (int i = 0; i < 20; i++) {
        long startTime = System.currentTimeMillis();
        init();
        Tour tour = pso();
//      if(tour.getDistence(distence)<872)
//      view(tour);
        System.out.println(tour);
        System.out.println(tour.bestDist);
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime) + " ms.");
//        }
    }

    //交换序定义(用于互换城市x和y位置)
    static class SwapSequence {
        int x;
        int y;

        public SwapSequence() {
        }

        public SwapSequence(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}
